package william.array;

/**
 * @author ZhangShenao
 * @date 2024/3/3
 * @description <a href="https://leetcode.cn/problems/minimum-size-subarray-sum/description/">...</a>
 */
public class Leetcode209_长度最小的子数组 {
    /**
     * 采用滑动窗口法
     * 在窗口[l,r]范围内,计算连续子数组的和,并与目标值进行比较
     * 如果加和>=目标值,则记录子数组长度,并将l右移,缩短子数组
     * 如果加和< 目标值,则r右移,扩充子数组
     * <p>
     * 时间复杂度O(N) 只遍历数组一次
     * 空间复杂度O(1)
     */
    public int minSubArrayLen(int target, int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1 || target <= 0) {
            return 0;
        }

        //窗口为[l,r],校验窗口内的子数组和是否>=target
        int l = 0;
        int r = -1;

        int N = nums.length;
        int sum = 0;
        int min = Integer.MAX_VALUE;//记录最小长度

        //遍历数组,调整窗口大小
        while (l < N) {
            if (sum >= target) { //当前窗口和>=target,记录当前窗口长度,并则将l右移,缩小窗口
                min = Math.min(min, (r - l) + 1);
                sum -= nums[l++];
            } else { //窗前窗口和<target,则将r右移,扩大窗口
                if (r >= N - 1) { //窗口以扩到最大,终止
                    break;
                }
                sum += nums[++r];
            }
        }

        if (min == Integer.MAX_VALUE) {   //没有满足条件的子数组,返回0
            return 0;
        }

        //返回最短长度
        return min;
    }
}
